public class MySingleList implements IList{
    //单向无头不循环链表
    //静态内部类
    //把结点抽象成一个内部类
    static  class ListNode{
        public int val;//数据域
        public ListNode next;//存放下一个结点的地址

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//成员变量是引用类型，默认初始值是null


    //创建一个链表
    //可以这样子写，也是可以实现插入方法进行创建一个链表
    public  void createList(){
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
    }



    //得到单链表的长度
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }


    //查找是否包含关键字key是否在单链表中
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null){
            if(cur.val == key){
                return true;//找到
            }
            //没有找到就出来，继续往后走
            cur = cur.next;
        }
        return false;
    }
    @Override
    public void display() {
        //最好用这种
        ListNode cur = head;//将头结点给到cur,让循环走下去，这样子head的指向不会发生改变
        while (cur != null){
            System.out.print(cur.val + "  ");
            cur = cur.next;
        }

        //这种方法head的指向会发生改变
        /*while (head != null){
            System.out.println(head.val + "");
            head = head.next;
        }*/
    }

    //从指定位置开始打印
    public void display2(ListNode newHead) {
        //最好用这种
        ListNode cur = newHead;//将头结点给到cur,让循环走下去，这样子head的指向不会发生改变
        while (cur != null) {
            System.out.print(cur.val + "  ");
            cur = cur.next;
        }
    }


    //头插
    @Override
    public void addFist(int data) {

        ListNode newnode = new ListNode(data);//创建一个新的结点
        //空链表也不会有问题
        newnode.next = head;
        head = newnode;

    }

    //尾插
    @Override
    public void addLast(int data) {
        ListNode cur = head;
        ListNode newnode = new ListNode(data);//创建一个新的结点
        if(head == null){
            head = newnode;
            return;
        }
        while(cur.next != null){//找尾巴
            cur = cur.next;
        }
        //如果cur下一个结点为空，就是走到最后了
        cur.next = newnode;

    }

    @Override
    //在指定位置插入一个值
    public void addIndex(int index, int data) {
        int len = size();
        if(index<0||index>len){//看插入的位置合法不
            System.out.println("index位置不合法");
            return;
        }
        if(index == 0){//代表头插
            addFist(data);
            return;
        }

        if(index == len){//代表尾插
            addLast(data);
            return;
        }

        //中间插入


        ListNode cur = head;
        while ((index-1) != 0){//找到插入位置的第一个前一个结点
            cur = cur.next;
            index--;
        }
        ListNode newnode = new ListNode(data);//创建一个新的结点
        //顺序不能换
        //规律所有的插入优先连后面
        //cur代表插入位置的前一个结点
        newnode.next = cur.next;
        cur.next = newnode;


        //下面的顺序就能随便换了
        /*ListNode  next  = null;
        next = cur.next;
        cur.next = newnode;
        newnode.next = next;*/


    }




    //删除的结点是局部变量不需要清空，系统会自动回收

    //删除第一次出现关键字key的结点
    @Override
    public void remove(int key) {
        if(head == null){
            return;//注意return不能少，否侧代码会一直执行
        }
        if(head.val == key){//如果第一个结点就是key
            head = head.next;//找到就是直接改变指针的执行
            return;//直接返回
        }
        ListNode cur = findNodeOfKey(key);//找key的前一个结点
        if(cur == null){//如果cur等与空，就是没有找到
            return;//
        }
        ListNode del = cur.next;//被删除的结点
        cur.next = del.next;//改变执向

    }
    private ListNode findNodeOfKey(int key) {//找结点

        ListNode cur = head;
        while (cur.next != null){
            if(cur.next.val == key){//找到key
                return  cur;//返回key的前一个结点
            }
            cur = cur.next;//cur的不断往下走
        }
        return null;//没有找到返回null
    }




    //删除所有的key
    @Override
    public void removeAllKey(int key) {
        if(head == null){
            return;
        }

        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;//删除
                cur = cur.next;//继续往下走
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        //放到最后才能删第一个
        if(head.val == key){//如果第一个结点就是key
            head = head.next;//找到就是直接改变指针的指向
        }
    }


    @Override
    public void clear() {
        ListNode cur = head;
        while (cur != null){
            ListNode curnext = cur.next;
            cur.next = null;
            cur = curnext;
        }
        head = null;
    }





    //反转单链表
    //利用头插法实现反转
    public ListNode reverseList() {
        if(head == null){
            return head;
        }
        ListNode cur = head.next;//定义一个cur指针保存head结点next域的地址
        head.next = null;//将头结点先置为空，因为反转链表这个就是尾结点，必须置为空

        while(cur != null){
            ListNode curnext = cur.next;
            cur.next  =  head;//将head的地址保存在cur.next
            head = cur;//头指针不断往一个移动，后一个不断成为头指针
            cur = curnext;//cur不断往下走
        }
        return head;
    }




    /*给你单链表的头结点 head ，请你找出并返回链表的中间结点。
    如果有两个中间结点，则返回第二个中间结点。*/
    public ListNode middleNode() {
        if(head == null){
            return head;
        }
        ListNode fast = head;//快指针
        ListNode slow = head;//慢指针
        while(fast != null && fast.next != null){
            fast = fast.next.next;//fast一次走两步
            slow = slow.next;//slow一次走一步

        }
        return slow;
    }





    //输入一个链表，输出该链表中倒数第k个结点。
    //方法2
    public int kthToLast(ListNode head, int k) {


        if(head == null) return -1;
        if(k <= 0) {
            return -1;
        }
        //这样写不好  你还得求链表的长度 ！！！！
        // if(k > 5) {
        //     return -1;
        // }
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while(count != k-1) {
            fast = fast.next;//fast指针先走k-1步


            if(fast == null) {
                return -1;
            }
            
            count++;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    //方法1
    public int kthToLast1(ListNode head, int k) {

        if(head == null){
            return 0;
        }
        ListNode fast = head;//快指针
        ListNode slow = head;//慢指针
        for(int i = 0 ; i < k; i++){//走k-1步
            fast = fast.next;

        }
        while(fast != null ){
            fast = fast.next;//fast走两步
            slow = slow.next;//slow走一步
        }
        return slow.val;


    }




    //现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
    // 且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(int x){

        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;//cur等与原来列表的头指针
        while(cur != null){
            if(cur.val < x){//小与x的分这里
                //bs == null就是第一次插入
                if(bs == null){//bs为空
                    bs = be = cur;//将第一个结点插入bs/be

                }else{
                    be.next = cur;//将下一个结点插入be
                    be = be.next;//be继续往下走一个位置
                }
            }else{//大于x的分这里
                if(as ==null){//as如果为空
                    as = ae = cur;//将大于x的结点放到as/ae这里
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs==null){
            return as;
        }
        //bs！= null
        be.next = as;
        //不管第二部部分的最后一个结点是否为空，都手动置为空
        if(as != null){
            ae.next = null;
        }
        return bs;

    }







    //对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
    //
    //给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
    //
    //测试样例：
    //1->2->2->1
    public boolean chkPalindrome() {


        if(head == null){
            return true;
        }

        //1。找到中间结点
        ListNode  fast = head;//快指针
        ListNode  slow = head;//满指针
        while (fast != null && fast.next!= null){

            fast = fast.next.next;//快指针一次走两步
            slow = slow.next;//慢指针一次走一步
        }//slow指向的位置就是中间结点

        //2.反转后一半的链表
        ListNode cur = slow.next;
        while(cur != null){
            //翻转
            ListNode curnext = cur.next;
            cur.next = slow;
            slow = cur;
            cur =  curnext;
        }

        //3.判断回文

        while (head != slow){//如果不相等就是继续走，如果相等就是相遇了，直接退出循环
             if(head.val != slow.val){
                 return false;
             }

             //值一样的情况下发现 和slow相等
            //直接解决了偶数问题
             if(head.next == slow){
                 return  true;
             }


             //如果一样就继续走
            head = head.next;
            slow = slow.next;
        }
        return  true;//最后就是回头链表了

    }





    //给你一个链表的头节点 head ，判断链表中是否有环。
    public boolean hasCycle() {

        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null && fast.next!= null ){

            fast = fast.next.next;//fast走两步
            slow = slow.next;//slow走一步
            if(fast == slow){//相遇点
                return true;
            }
        }
        return false;

    }
    //创建环
    public void createLoop(){
        ListNode cur = head;
        while(cur.next != null){//找到最后一个结点
            cur = cur.next;
        }
        cur.next = head.next.next;
    }



   // 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
    public ListNode detectCycle() {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {//相遇点
                break;
            }
        }
        //走到这里要么相遇了，要么没有环


        if (fast == null || fast.next == null) {//如果循环条件没有满足，就是没有环
            return null;
        }
        //相遇了，有环
        fast = head;//把一个拿到头结点
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;

        }
        //相等就是走到那个交点了
        return fast;
    }



}
